package backtrack

func solveNQueens(n int) [][]string {
    res := [][]string{}
    board := make([][]byte, n)
	for i := range board {
		board[i] = make([]byte, n)
		for j := range board[i] {
			board[i][j] = '.'
		}
	}
	var dfs func(row int)
	dfs = func(row int) {
		if row == n {
			list := make([]string, n)
			for i := range board {
				list[i] = string(board[i])
			}
			res = append(res, list)
			return
		}
		for col := 0; col < n; col++ {
			if isValid(row, col, n, board) {
				board[row][col] = 'Q'
				dfs(row + 1)
				board[row][col] = '.'
			}
		}
	}
	dfs(0)
	return res
}

func isValid(row, col, n int, board [][]byte) bool {
	for i := 0; i < row; i++ {
		if board[i][col] == 'Q' {
			return false
		}
	}
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if board[i][j] == 'Q' {
			return false
		}
	}
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if board[i][j] == 'Q' {
			return false
		}
	}
	return true
}
